package com.leetcode.p100;

import com.bean.ListNode;
import com.utils.DataUtils;

public class Test147 {

    public ListNode insertionSortList(ListNode head) {
        ListNode dummyNode = new ListNode();
        dummyNode.next = head;

        ListNode cur = dummyNode.next;
        ListNode lastNode = head;

        while (cur != null) {
            if (lastNode.val <=cur.val){
                lastNode = cur;
            } else{
                ListNode pre = dummyNode;

                while (pre.next.val < cur.val) {
                    pre = pre.next;
                }

                lastNode.next = cur.next;
                cur.next = pre.next;
                pre.next = cur;
            }

            cur = lastNode.next;
        }

        return dummyNode.next;
    }

    public static void main(String[] args) {
//        ListNode listNode1 = DataUtils.getOneToNumberListNode(2);
        ListNode listNode1 = DataUtils.getListNode(new int[]{4, 5, -1, 2, 9});

        Test147 test21 = new Test147();
        ListNode list = test21.insertionSortList(listNode1);
        DataUtils.printListNode(list);
    }

}
